package _01_第一季.栈与队列03;

import _01_第一季._00_公共接口.Queue;
/**
 * 循环队列
 * @param <E>
 */
@SuppressWarnings("unchecked")
public class ArrayLoopQueue<E> implements Queue<E> {
    private E[] elements;
    private int size;
    private int front;
    private static final int DEFAULT_CAPACITY = 10;

    public ArrayLoopQueue(){
        this(DEFAULT_CAPACITY);
    }

    public ArrayLoopQueue(int capacity){
        capacity = Math.max(capacity,DEFAULT_CAPACITY);
        elements = (E[]) new Object[capacity];
        front = 0;
        size = 0;
    }
    @Override
    public int size() {
        return size;
    }

    @Override
    public boolean isEmpty() {
        return size == 0;
    }

    private int index(int index){
        index += front;
        return index - (index >= elements.length ? elements.length : 0);
    }

    @Override
    public void clear() {
        for(int i=0;i<size;++i){
            elements[index(i)] = null;
        }
        size = 0;
        front = 0;

        if(elements!=null && elements.length>DEFAULT_CAPACITY){
            elements = (E[]) new Object[DEFAULT_CAPACITY];
        }
    }

    //从队尾进入
    @Override
    public void enQueue(E element) {
        enSureCapacity(size+1);
        elements[index(size)] = element;
        size++;
    }

    //内部扩容
    private void enSureCapacity(int capacity) {
        int oldCapacity = elements.length;
        if(oldCapacity>=capacity) return;
        int newCapacity = oldCapacity + (oldCapacity>>1);
        E[] newElements = (E[]) new Object[newCapacity];
        for(int i=0;i<size;++i){
            newElements[i] = elements[(i+front)% elements.length];
        }
        elements = newElements;
        front = 0;
        System.out.println(oldCapacity+"扩容尾:"+newCapacity);
    }

    @Override
    public E deQueue() {
        E ret = elements[front];
        elements[front] = null;
        front = index(1);
        size--;
        return ret;
    }

    @Override
    public E front() {
        return elements[front];
    }

    @Override
    public String toString() {
        StringBuilder sb = new StringBuilder();

        sb.append("capacity= ").append(elements.length).append(" size= ")
                .append(size).append(" front= ").append(front)
                .append(", [");
        for(int i=0;i<elements.length;++i){
            if(i!=0){
                sb.append(',');
            }
            sb.append(elements[i]);
        }
        sb.append(']');

        return sb.toString();
    }
}
